package myList1;

public class MergeLinkedList {
    public static void main(String[] args) {
        Integer[] a = {1, 2, 3, 4, 5};
        Integer[] b = {2, 4, 6, 8, 10};
        MyLinkedList<Integer> lA = new MyLinkedList<Integer>();
        MyLinkedList<Integer> lB = new MyLinkedList<Integer>();
        lA.createListR(a);
        lB.createListR(b);
        MyLinkedList<Integer> lC = merge2(lA, lB);
        MyLinkedList<Integer> lD = comMerge(lA, lB);
        System.out.println("lc: " + lC);
        System.out.println("ld: " + lD);
    }

    public static MyLinkedList<Integer> merge2(MyLinkedList<Integer> listA,
                                               MyLinkedList<Integer> listB) {
        LinkNode<Integer> p = listA.head.next;    //p指向A的首结点
        LinkNode<Integer> q = listB.head.next;    //q指向B的首结点
        MyLinkedList<Integer> listC = new MyLinkedList<Integer>();
        LinkNode<Integer> t = listC.head;    //t为C的尾结点
        while (p != null && q != null)        //两个单链表都没有遍历完
        {
            if (p.data < q.data)        //将较小结点p链接到C的末尾
            {
                t.next = p;
                t = p;
                p = p.next;
            } else                //将较小结点q链接到C的末尾
            {
                t.next = q;
                t = q;
                q = q.next;
            }
        }
        t.next = null;            //尾结点next置空
        if (p != null) t.next = p;
        if (q != null) t.next = q;
        return listC;
    }

    public static MyLinkedList<Integer> comMerge(
            MyLinkedList<Integer> listA, MyLinkedList<Integer> listB) {
        LinkNode<Integer> p = listA.head.next;    //p指向A的首结点
        LinkNode<Integer> q = listB.head.next;    //q指向B的首结点
        MyLinkedList<Integer> listC = new MyLinkedList<Integer>();
        LinkNode<Integer> t = listC.head;    //t为C的尾结点
        while (p != null && q != null)        //两个单链表都没有遍历完
        {
            if (p.data < q.data)        //跳过较小的p结点p链接到C的末尾
                p = p.next;
            else if (q.data < p.data)        //将较小结点q链接到C的末尾
                q = q.next;
            else                //p结点和q结点值相同
            {
                LinkNode<Integer> s = new LinkNode<Integer>(p.data);    //新建s结点
                t.next = s;
                t = s;            //将s结点链接到C的末尾
                p = p.next;
                q = q.next;
            }
        }
        t.next = null;                //尾结点next置空
        return listC;
    }

}


